package cn.lbd.arithmetic.leetcode.editor.cn;
//给你一个由 不同 整数组成的整数数组 arr 和一个整数 k 。
//
// 每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的
//胜利并保留在位置 0 ，较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的 赢家 。 
//
// 返回赢得比赛的整数。 
//
// 题目数据 保证 游戏存在赢家。 
//
// 
//
// 示例 1： 
//
// 输入：arr = [2,1,3,5,4,6,7], k = 2
//输出：5
//解释：一起看一下本场游戏每回合的情况：
//
//因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合。
// 
//
// 示例 2： 
//
// 输入：arr = [3,2,1], k = 10
//输出：3
//解释：3 将会在前 10 个回合中连续获胜。
// 
//
// 示例 3： 
//
// 输入：arr = [1,9,8,2,3,7,6,4,5], k = 7
//输出：9
// 
//
// 示例 4： 
//
// 输入：arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
//输出：99
// 
//
// 
//
// 提示： 
//
// 
// 2 <= arr.length <= 10^5 
// 1 <= arr[i] <= 10^6 
// arr 所含的整数 各不相同 。 
// 1 <= k <= 10^9 
// 
// Related Topics 数组 
// 👍 18 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution1535 {
    public static int getWinner(int[] arr, int k) {
        //上一轮游戏的胜利者,初始值给的是第一轮游戏的获胜者
        int prev = Math.max(arr[0],arr[1]);
        //上轮赢家的连胜次数
        int count = 0;
        //最大的数，循环中迭代更新
        int maxNum = 0;
        //打擂者
        int currentNum = 0;
        //如果只有两个元素或者只要比一次，就只要返回前两个元素大的那一个
        if (arr.length == 2 || k == 1) {
            return Math.max(arr[0],arr[1]);
        }
        //第一轮判断在赋默认值时完成，现在直接从第三个元素 与 前两个元素的获胜者开始对比
        for (int i = 2; i < arr.length; i++) {
            currentNum = arr[i];
            //记录的是上把游戏获胜者的连胜次数，对其连胜次数的更新，在这一把完成，因此count在这里自增
            count++;
            //要在每轮游戏前（更新每轮胜者前）去判断是否已达到连胜次数，否则万一后面的胜者被替换，连赢次数会被更新成0，就会出错
            if (count >= k) {
                return maxNum;
            }
            //如果prev依旧大于这一轮的打擂者，就不动prev，并在下一轮一开始，去判断他的连胜次数以及是否获胜
            //如果小于这一轮打擂者，说明这一轮的打擂者是本轮游戏的赢家，count记录的是上轮赢家的连胜次数，因此要做两件事
            //1. 更新prev为本轮赢家  2. 将记录之前prev的count置为0
            if (prev < currentNum) {
                count = 0;
                prev = currentNum;
            }
            //更新最大值，prev每一轮必定一直变大，直到遍历完数组变成最大
            maxNum = prev;
        }
        return maxNum;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1,9,8,2,3,7,6,4,5};
        int k = 7;
        System.out.println(getWinner(arr, k));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
